package com.peng.leetcode.unionFind;

import java.util.Arrays;

/**
 * FindRedundantConnection
 *
 * 684. 冗余连接
 *
 * 在本问题中, 树指的是一个连通且无环的无向图。
 *
 * 输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
 *
 * 结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。
 *
 * 返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。
 *
 * 链接：https://leetcode-cn.com/problems/redundant-connection
 *
 * @author: lupeng6
 * @create: 2021/1/11 22:19
 */
public class FindRedundantConnection {

    public static void main(String[] args) {
        int[][] edges = {{1,2}, {1,3}, {2,3}};
        int[] redundantConnection = new FindRedundantConnection().findRedundantConnection(edges);
        Arrays.stream(redundantConnection).forEach(System.out::println);
    }

    int[] result = new int[2];

    int[] parent;

    public int[] findRedundantConnection(int[][] edges) {
        parent = new int[edges.length + 1];
        for (int i = 0; i < edges.length; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < edges.length; i++) {
            int[] edge = edges[i];
            int point1 = edge[0];
            int point2 = edge[1];

            int root1 = find(point1);
            int root2 = find(point2);
            if (root1 != root2) {
                parent[root1] = root2;
            } else {
                result[0] = point1;
                result[1] = point2;
            }
        }

        return result;
    }

    private int find(int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

}
